package main

import (
	"fmt"
	util "go-algorithm-practice/0_util"
)

// 插入排序
//
// 0～0
// 1～0
// 2～0

func InsertSort(arr []int) []int {
	if arr == nil || len(arr) < 2 {
		return arr
	}

	for i := 1; i < len(arr); i++ {
		for j := i - 1; j >= 0 && arr[j] > arr[j+1]; j-- {
			arr[j+1], arr[j] = arr[j], arr[j+1]
		}
	}
	return arr

}

func main() {
	fmt.Println(InsertSort([]int{1000, 3000, 1, 2, 3, 10, 9, 8, 6}))
	fmt.Println(InsertSort([]int{9, 8, 7, 7, 6, 8, 4}))
	fmt.Println(InsertSort([]int{100, 20, 6, 10, 9, 8, 6}))
	for i := 0; i < 10; i++ {
		fmt.Println("res: ", InsertSort(util.RandomArray(10)))
	}
}
